{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第10章 隐马尔可夫模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1．隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态的序列，再由各个状态随机生成一个观测而产生观测的序列的过程。\n",
    "\n",
    "隐马尔可夫模型由初始状态概率向$\\pi$、状态转移概率矩阵$A$和观测概率矩阵$B$决定。因此，隐马尔可夫模型可以写成$\\lambda=(A, B, \\pi)$。\n",
    "\n",
    "隐马尔可夫模型是一个生成模型，表示状态序列和观测序列的联合分布，但是状态序列是隐藏的，不可观测的。\n",
    "\n",
    "隐马尔可夫模型可以用于标注，这时状态对应着标记。标注问题是给定观测序列预测其对应的标记序列。\n",
    "\n",
    "2．概率计算问题。给定模型$\\lambda=(A, B, \\pi)$和观测序列$O＝(o_1，o_2,…,o_T)$，计算在模型$\\lambda$下观测序列$O$出现的概率$P(O|\\lambda)$。前向-后向算法是通过递推地计算前向-后向概率可以高效地进行隐马尔可夫模型的概率计算。\n",
    " \n",
    "3．学习问题。已知观测序列$O＝(o_1，o_2,…,o_T)$，估计模型$\\lambda=(A, B, \\pi)$参数，使得在该模型下观测序列概率$P(O|\\lambda)$最大。即用极大似然估计的方法估计参数。Baum-Welch算法，也就是EM算法可以高效地对隐马尔可夫模型进行训练。它是一种非监督学习算法。\n",
    "\n",
    "4．预测问题。已知模型$\\lambda=(A, B, \\pi)$和观测序列$O＝(o_1，o_2,…,o_T)$，求对给定观测序列条件概率$P(I|O)$最大的状态序列$I＝(i_1，i_2,…,i_T)$。维特比算法应用动态规划高效地求解最优路径，即概率最大的状态序列。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class HiddenMarkov:\n",
    "    def forward(self, Q, V, A, B, O, PI):  # 使用前向算法\n",
    "        N = len(Q)  #可能存在的状态数量\n",
    "        M = len(O)  # 观测序列的大小\n",
    "        alphas = np.zeros((N, M))  # alpha值\n",
    "        T = M  # 有几个时刻，有几个观测序列，就有几个时刻\n",
    "        for t in range(T):  # 遍历每一时刻，算出alpha值\n",
    "            indexOfO = V.index(O[t])  # 找出序列对应的索引\n",
    "            for i in range(N):\n",
    "                if t == 0:  # 计算初值\n",
    "                    alphas[i][t] = PI[t][i] * B[i][indexOfO]  # P176（10.15）\n",
    "                    print(\n",
    "                        'alpha1(%d)=p%db%db(o1)=%f' % (i, i, i, alphas[i][t]))\n",
    "                else:\n",
    "                    alphas[i][t] = np.dot(\n",
    "                        [alpha[t - 1] for alpha in alphas],\n",
    "                        [a[i] for a in A]) * B[i][indexOfO]  # 对应P176（10.16）\n",
    "                    print('alpha%d(%d)=[sigma alpha%d(i)ai%d]b%d(o%d)=%f' %\n",
    "                          (t, i, t - 1, i, i, t, alphas[i][t]))\n",
    "                    # print(alphas)\n",
    "        P = np.sum([alpha[M - 1] for alpha in alphas])  # P176(10.17)\n",
    "        # alpha11 = pi[0][0] * B[0][0]    #代表a1(1)\n",
    "        # alpha12 = pi[0][1] * B[1][0]    #代表a1(2)\n",
    "        # alpha13 = pi[0][2] * B[2][0]    #代表a1(3)\n",
    "\n",
    "    def backward(self, Q, V, A, B, O, PI):  # 后向算法\n",
    "        N = len(Q)  # 可能存在的状态数量\n",
    "        M = len(O)  # 观测序列的大小\n",
    "        betas = np.ones((N, M))  # beta\n",
    "        for i in range(N):\n",
    "            print('beta%d(%d)=1' % (M, i))\n",
    "        for t in range(M - 2, -1, -1):\n",
    "            indexOfO = V.index(O[t + 1])  # 找出序列对应的索引\n",
    "            for i in range(N):\n",
    "                betas[i][t] = np.dot(\n",
    "                    np.multiply(A[i], [b[indexOfO] for b in B]),\n",
    "                    [beta[t + 1] for beta in betas])\n",
    "                realT = t + 1\n",
    "                realI = i + 1\n",
    "                print(\n",
    "                    'beta%d(%d)=[sigma a%djbj(o%d)]beta%d(j)=(' %\n",
    "                    (realT, realI, realI, realT + 1, realT + 1),\n",
    "                    end='')\n",
    "                for j in range(N):\n",
    "                    print(\n",
    "                        \"%.2f*%.2f*%.2f+\" % (A[i][j], B[j][indexOfO],\n",
    "                                             betas[j][t + 1]),\n",
    "                        end='')\n",
    "                print(\"0)=%.3f\" % betas[i][t])\n",
    "        # print(betas)\n",
    "        indexOfO = V.index(O[0])\n",
    "        P = np.dot(\n",
    "            np.multiply(PI, [b[indexOfO] for b in B]),\n",
    "            [beta[0] for beta in betas])\n",
    "        print(\"P(O|lambda)=\", end=\"\")\n",
    "        for i in range(N):\n",
    "            print(\n",
    "                \"%.1f*%.1f*%.5f+\" % (PI[0][i], B[i][indexOfO], betas[i][0]),\n",
    "                end=\"\")\n",
    "        print(\"0=%f\" % P)\n",
    "\n",
    "    def viterbi(self, Q, V, A, B, O, PI):\n",
    "        N = len(Q)  #可能存在的状态数量\n",
    "        M = len(O)  # 观测序列的大小\n",
    "        deltas = np.zeros((N, M))\n",
    "        psis = np.zeros((N, M))\n",
    "        I = np.zeros((1, M))\n",
    "        for t in range(M):\n",
    "            realT = t + 1\n",
    "            indexOfO = V.index(O[t])  # 找出序列对应的索引\n",
    "            for i in range(N):\n",
    "                realI = i + 1\n",
    "                if t == 0:\n",
    "                    deltas[i][t] = PI[0][i] * B[i][indexOfO]\n",
    "                    psis[i][t] = 0\n",
    "                    print('delta1(%d)=pi%d * b%d(o1)=%.2f * %.2f=%.2f' %\n",
    "                          (realI, realI, realI, PI[0][i], B[i][indexOfO],\n",
    "                           deltas[i][t]))\n",
    "                    print('psis1(%d)=0' % (realI))\n",
    "                else:\n",
    "                    deltas[i][t] = np.max(\n",
    "                        np.multiply([delta[t - 1] for delta in deltas],\n",
    "                                    [a[i] for a in A])) * B[i][indexOfO]\n",
    "                    print(\n",
    "                        'delta%d(%d)=max[delta%d(j)aj%d]b%d(o%d)=%.2f*%.2f=%.5f'\n",
    "                        % (realT, realI, realT - 1, realI, realI, realT,\n",
    "                           np.max(\n",
    "                               np.multiply([delta[t - 1] for delta in deltas],\n",
    "                                           [a[i] for a in A])), B[i][indexOfO],\n",
    "                           deltas[i][t]))\n",
    "                    psis[i][t] = np.argmax(\n",
    "                        np.multiply(\n",
    "                            [delta[t - 1] for delta in deltas],\n",
    "                            [a[i]\n",
    "                             for a in A])) + 1  #由于其返回的是索引，因此应+1才能和正常的下标值相符合。\n",
    "                    print('psis%d(%d)=argmax[delta%d(j)aj%d]=%d' %\n",
    "                          (realT, realI, realT - 1, realI, psis[i][t]))\n",
    "        print(deltas)\n",
    "        print(psis)\n",
    "        I[0][M - 1] = np.argmax([delta[M - 1] for delta in deltas\n",
    "                                 ]) + 1  #由于其返回的是索引，因此应+1才能和正常的下标值相符合。\n",
    "        print('i%d=argmax[deltaT(i)]=%d' % (M, I[0][M - 1]))\n",
    "        for t in range(M - 2, -1, -1):\n",
    "            I[0][t] = psis[int(I[0][t + 1]) - 1][t + 1]\n",
    "            print('i%d=psis%d(i%d)=%d' % (t + 1, t + 2, t + 2, I[0][t]))\n",
    "        print(\"状态序列I：\", I)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题10.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#习题10.1\n",
    "Q = [1, 2, 3]\n",
    "V = ['红', '白']\n",
    "A = [[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]]\n",
    "B = [[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]]\n",
    "# O = ['红', '白', '红', '红', '白', '红', '白', '白']\n",
    "O = ['红', '白', '红', '白']    #习题10.1的例子\n",
    "PI = [[0.2, 0.4, 0.4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "delta1(1)=pi1 * b1(o1)=0.20 * 0.50=0.10\n",
      "psis1(1)=0\n",
      "delta1(2)=pi2 * b2(o1)=0.40 * 0.40=0.16\n",
      "psis1(2)=0\n",
      "delta1(3)=pi3 * b3(o1)=0.40 * 0.70=0.28\n",
      "psis1(3)=0\n",
      "delta2(1)=max[delta1(j)aj1]b1(o2)=0.06*0.50=0.02800\n",
      "psis2(1)=argmax[delta1(j)aj1]=3\n",
      "delta2(2)=max[delta1(j)aj2]b2(o2)=0.08*0.60=0.05040\n",
      "psis2(2)=argmax[delta1(j)aj2]=3\n",
      "delta2(3)=max[delta1(j)aj3]b3(o2)=0.14*0.30=0.04200\n",
      "psis2(3)=argmax[delta1(j)aj3]=3\n",
      "delta3(1)=max[delta2(j)aj1]b1(o3)=0.02*0.50=0.00756\n",
      "psis3(1)=argmax[delta2(j)aj1]=2\n",
      "delta3(2)=max[delta2(j)aj2]b2(o3)=0.03*0.40=0.01008\n",
      "psis3(2)=argmax[delta2(j)aj2]=2\n",
      "delta3(3)=max[delta2(j)aj3]b3(o3)=0.02*0.70=0.01470\n",
      "psis3(3)=argmax[delta2(j)aj3]=3\n",
      "delta4(1)=max[delta3(j)aj1]b1(o4)=0.00*0.50=0.00189\n",
      "psis4(1)=argmax[delta3(j)aj1]=1\n",
      "delta4(2)=max[delta3(j)aj2]b2(o4)=0.01*0.60=0.00302\n",
      "psis4(2)=argmax[delta3(j)aj2]=2\n",
      "delta4(3)=max[delta3(j)aj3]b3(o4)=0.01*0.30=0.00220\n",
      "psis4(3)=argmax[delta3(j)aj3]=3\n",
      "[[0.1      0.028    0.00756  0.00189 ]\n",
      " [0.16     0.0504   0.01008  0.003024]\n",
      " [0.28     0.042    0.0147   0.002205]]\n",
      "[[0. 3. 2. 1.]\n",
      " [0. 3. 2. 2.]\n",
      " [0. 3. 3. 3.]]\n",
      "i4=argmax[deltaT(i)]=2\n",
      "i3=psis4(i4)=2\n",
      "i2=psis3(i3)=2\n",
      "i1=psis2(i2)=3\n",
      "状态序列I： [[3. 2. 2. 2.]]\n"
     ]
    }
   ],
   "source": [
    "HMM = HiddenMarkov()\n",
    "# HMM.forward(Q, V, A, B, O, PI)\n",
    "# HMM.backward(Q, V, A, B, O, PI)\n",
    "HMM.viterbi(Q, V, A, B, O, PI)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 习题10.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = [1, 2, 3]\n",
    "V = ['红', '白']\n",
    "A = [[0.5, 0.2, 0.3], [0.3, 0.5, 0.2], [0.2, 0.3, 0.5]]\n",
    "B = [[0.5, 0.5], [0.4, 0.6], [0.7, 0.3]]\n",
    "O = ['红', '白', '红', '红', '白', '红', '白', '白']\n",
    "PI = [[0.2, 0.3, 0.5]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alpha1(0)=p0b0b(o1)=0.100000\n",
      "alpha1(1)=p1b1b(o1)=0.120000\n",
      "alpha1(2)=p2b2b(o1)=0.350000\n",
      "alpha1(0)=[sigma alpha0(i)ai0]b0(o1)=0.078000\n",
      "alpha1(1)=[sigma alpha0(i)ai1]b1(o1)=0.111000\n",
      "alpha1(2)=[sigma alpha0(i)ai2]b2(o1)=0.068700\n",
      "alpha2(0)=[sigma alpha1(i)ai0]b0(o2)=0.043020\n",
      "alpha2(1)=[sigma alpha1(i)ai1]b1(o2)=0.036684\n",
      "alpha2(2)=[sigma alpha1(i)ai2]b2(o2)=0.055965\n",
      "alpha3(0)=[sigma alpha2(i)ai0]b0(o3)=0.021854\n",
      "alpha3(1)=[sigma alpha2(i)ai1]b1(o3)=0.017494\n",
      "alpha3(2)=[sigma alpha2(i)ai2]b2(o3)=0.033758\n",
      "alpha4(0)=[sigma alpha3(i)ai0]b0(o4)=0.011463\n",
      "alpha4(1)=[sigma alpha3(i)ai1]b1(o4)=0.013947\n",
      "alpha4(2)=[sigma alpha3(i)ai2]b2(o4)=0.008080\n",
      "alpha5(0)=[sigma alpha4(i)ai0]b0(o5)=0.005766\n",
      "alpha5(1)=[sigma alpha4(i)ai1]b1(o5)=0.004676\n",
      "alpha5(2)=[sigma alpha4(i)ai2]b2(o5)=0.007188\n",
      "alpha6(0)=[sigma alpha5(i)ai0]b0(o6)=0.002862\n",
      "alpha6(1)=[sigma alpha5(i)ai1]b1(o6)=0.003389\n",
      "alpha6(2)=[sigma alpha5(i)ai2]b2(o6)=0.001878\n",
      "alpha7(0)=[sigma alpha6(i)ai0]b0(o7)=0.001411\n",
      "alpha7(1)=[sigma alpha6(i)ai1]b1(o7)=0.001698\n",
      "alpha7(2)=[sigma alpha6(i)ai2]b2(o7)=0.000743\n",
      "beta8(0)=1\n",
      "beta8(1)=1\n",
      "beta8(2)=1\n",
      "beta7(1)=[sigma a1jbj(o8)]beta8(j)=(0.50*0.50*1.00+0.20*0.60*1.00+0.30*0.30*1.00+0)=0.460\n",
      "beta7(2)=[sigma a2jbj(o8)]beta8(j)=(0.30*0.50*1.00+0.50*0.60*1.00+0.20*0.30*1.00+0)=0.510\n",
      "beta7(3)=[sigma a3jbj(o8)]beta8(j)=(0.20*0.50*1.00+0.30*0.60*1.00+0.50*0.30*1.00+0)=0.430\n",
      "beta6(1)=[sigma a1jbj(o7)]beta7(j)=(0.50*0.50*0.46+0.20*0.60*0.51+0.30*0.30*0.43+0)=0.215\n",
      "beta6(2)=[sigma a2jbj(o7)]beta7(j)=(0.30*0.50*0.46+0.50*0.60*0.51+0.20*0.30*0.43+0)=0.248\n",
      "beta6(3)=[sigma a3jbj(o7)]beta7(j)=(0.20*0.50*0.46+0.30*0.60*0.51+0.50*0.30*0.43+0)=0.202\n",
      "beta5(1)=[sigma a1jbj(o6)]beta6(j)=(0.50*0.50*0.21+0.20*0.40*0.25+0.30*0.70*0.20+0)=0.116\n",
      "beta5(2)=[sigma a2jbj(o6)]beta6(j)=(0.30*0.50*0.21+0.50*0.40*0.25+0.20*0.70*0.20+0)=0.110\n",
      "beta5(3)=[sigma a3jbj(o6)]beta6(j)=(0.20*0.50*0.21+0.30*0.40*0.25+0.50*0.70*0.20+0)=0.122\n",
      "beta4(1)=[sigma a1jbj(o5)]beta5(j)=(0.50*0.50*0.12+0.20*0.60*0.11+0.30*0.30*0.12+0)=0.053\n",
      "beta4(2)=[sigma a2jbj(o5)]beta5(j)=(0.30*0.50*0.12+0.50*0.60*0.11+0.20*0.30*0.12+0)=0.058\n",
      "beta4(3)=[sigma a3jbj(o5)]beta5(j)=(0.20*0.50*0.12+0.30*0.60*0.11+0.50*0.30*0.12+0)=0.050\n",
      "beta3(1)=[sigma a1jbj(o4)]beta4(j)=(0.50*0.50*0.05+0.20*0.40*0.06+0.30*0.70*0.05+0)=0.028\n",
      "beta3(2)=[sigma a2jbj(o4)]beta4(j)=(0.30*0.50*0.05+0.50*0.40*0.06+0.20*0.70*0.05+0)=0.026\n",
      "beta3(3)=[sigma a3jbj(o4)]beta4(j)=(0.20*0.50*0.05+0.30*0.40*0.06+0.50*0.70*0.05+0)=0.030\n",
      "beta2(1)=[sigma a1jbj(o3)]beta3(j)=(0.50*0.50*0.03+0.20*0.40*0.03+0.30*0.70*0.03+0)=0.015\n",
      "beta2(2)=[sigma a2jbj(o3)]beta3(j)=(0.30*0.50*0.03+0.50*0.40*0.03+0.20*0.70*0.03+0)=0.014\n",
      "beta2(3)=[sigma a3jbj(o3)]beta3(j)=(0.20*0.50*0.03+0.30*0.40*0.03+0.50*0.70*0.03+0)=0.016\n",
      "beta1(1)=[sigma a1jbj(o2)]beta2(j)=(0.50*0.50*0.02+0.20*0.60*0.01+0.30*0.30*0.02+0)=0.007\n",
      "beta1(2)=[sigma a2jbj(o2)]beta2(j)=(0.30*0.50*0.02+0.50*0.60*0.01+0.20*0.30*0.02+0)=0.007\n",
      "beta1(3)=[sigma a3jbj(o2)]beta2(j)=(0.20*0.50*0.02+0.30*0.60*0.01+0.50*0.30*0.02+0)=0.006\n",
      "P(O|lambda)=0.2*0.5*0.00698+0.3*0.4*0.00741+0.5*0.7*0.00647+0=0.003852\n"
     ]
    }
   ],
   "source": [
    "HMM.forward(Q, V, A, B, O, PI)\n",
    "HMM.backward(Q, V, A, B, O, PI)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "参考代码：https://blog.csdn.net/tudaodiaozhale\n",
    "\n",
    "中文注释制作：机器学习初学者\n",
    "\n",
    "微信公众号：ID:ai-start-com\n",
    "\n",
    "配置环境：python 3.5+\n",
    "\n",
    "代码全部测试通过。\n",
    "![gongzhong](../gongzhong.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Package                            Version    \n",
      "---------------------------------- -----------\n",
      "-umpy                              1.14.2     \n",
      "absl-py                            0.1.13     \n",
      "alabaster                          0.7.10     \n",
      "anaconda-client                    1.6.9      \n",
      "anaconda-navigator                 1.7.0      \n",
      "anaconda-project                   0.8.2      \n",
      "appdirs                            1.4.3      \n",
      "asn1crypto                         0.24.0     \n",
      "astor                              0.6.2      \n",
      "astroid                            1.6.1      \n",
      "astropy                            2.0.3      \n",
      "attrs                              19.1.0     \n",
      "audioread                          2.1.5      \n",
      "autopep8                           1.4.3      \n",
      "Babel                              2.5.3      \n",
      "backports.shutil-get-terminal-size 1.0.0      \n",
      "basemap                            1.1.0      \n",
      "beautifulsoup4                     4.6.0      \n",
      "bitarray                           0.8.1      \n",
      "bkcharts                           0.2        \n",
      "black                              19.3b0     \n",
      "blaze                              0.11.3     \n",
      "bleach                             1.5.0      \n",
      "blis                               0.2.4      \n",
      "bokeh                              0.12.13    \n",
      "boto                               2.48.0     \n",
      "boto3                              1.6.16     \n",
      "botocore                           1.9.16     \n",
      "Bottleneck                         1.2.1      \n",
      "branca                             0.3.1      \n",
      "brewer2mpl                         1.4.1      \n",
      "bs4                                0.0.1      \n",
      "bz2file                            0.98       \n",
      "cachetools                         3.1.1      \n",
      "certifi                            2018.11.29 \n",
      "cffi                               1.11.4     \n",
      "chardet                            3.0.4      \n",
      "click                              6.7        \n",
      "cloudpickle                        0.5.2      \n",
      "clyent                             1.2.2      \n",
      "colorama                           0.3.9      \n",
      "comtypes                           1.1.4      \n",
      "conda                              4.4.10     \n",
      "conda-build                        3.4.1      \n",
      "conda-verify                       2.0.0      \n",
      "contextlib2                        0.5.5      \n",
      "cryptography                       2.1.4      \n",
      "cssselect                          1.0.3      \n",
      "cycler                             0.10.0     \n",
      "cymem                              2.0.2      \n",
      "Cython                             0.27.3     \n",
      "cytoolz                            0.9.0      \n",
      "dask                               0.16.1     \n",
      "datashape                          0.5.4      \n",
      "decorator                          4.2.1      \n",
      "dill                               0.2.9      \n",
      "distributed                        1.20.2     \n",
      "dlib                               19.13.1    \n",
      "docutils                           0.14       \n",
      "dopamine-rl                        2.0.5      \n",
      "entrypoints                        0.2.3      \n",
      "enum34                             1.1.6      \n",
      "et-xmlfile                         1.0.1      \n",
      "face-recognition                   1.2.2      \n",
      "face-recognition-models            0.3.0      \n",
      "Faker                              0.8.13     \n",
      "fastcache                          1.0.2      \n",
      "fasttext                           0.8.3      \n",
      "filelock                           2.0.13     \n",
      "fire                               0.1.3      \n",
      "Flask                              0.12.2     \n",
      "Flask-Cors                         3.0.3      \n",
      "folium                             0.7.0      \n",
      "funcsigs                           1.0.2      \n",
      "future                             0.16.0     \n",
      "fuzzywuzzy                         0.16.0     \n",
      "gast                               0.2.0      \n",
      "gensim                             3.4.0      \n",
      "get                                1.0.3      \n",
      "gevent                             1.2.2      \n",
      "gin-config                         0.1.4      \n",
      "glob2                              0.6        \n",
      "google-api-python-client           1.7.9      \n",
      "google-auth                        1.6.3      \n",
      "google-auth-httplib2               0.0.3      \n",
      "googleapis-common-protos           1.6.0      \n",
      "graphviz                           0.10.1     \n",
      "greenlet                           0.4.12     \n",
      "grpcio                             1.10.0     \n",
      "gunicorn                           19.9.0     \n",
      "gym                                0.12.5     \n",
      "h5py                               2.7.1      \n",
      "heapdict                           1.0.0      \n",
      "hmmlearn                           0.2.0      \n",
      "html5lib                           0.9999999  \n",
      "httplib2                           0.13.0     \n",
      "idna                               2.6        \n",
      "imageio                            2.2.0      \n",
      "imagesize                          0.7.1      \n",
      "imbalanced-learn                   0.4.3      \n",
      "imblearn                           0.0        \n",
      "ipykernel                          4.8.2      \n",
      "ipython                            6.2.1      \n",
      "ipython-genutils                   0.2.0      \n",
      "ipywidgets                         7.1.1      \n",
      "isort                              4.2.15     \n",
      "itsdangerous                       0.24       \n",
      "jdcal                              1.3        \n",
      "jedi                               0.11.1     \n",
      "jieba                              0.39       \n",
      "Jinja2                             2.10       \n",
      "jmespath                           0.9.3      \n",
      "joblib                             0.11       \n",
      "jsonschema                         2.6.0      \n",
      "jupyter                            1.0.0      \n",
      "jupyter-client                     5.2.2      \n",
      "jupyter-console                    5.2.0      \n",
      "jupyter-contrib-core               0.3.3      \n",
      "jupyter-contrib-nbextensions       0.5.1      \n",
      "jupyter-core                       4.4.0      \n",
      "jupyter-highlight-selected-word    0.2.0      \n",
      "jupyter-latex-envs                 1.4.6      \n",
      "jupyter-nbextensions-configurator  0.4.1      \n",
      "jupyterlab                         0.31.4     \n",
      "jupyterlab-launcher                0.10.2     \n",
      "Keras                              2.1.5      \n",
      "kfac                               0.1.4      \n",
      "lazy-object-proxy                  1.3.1      \n",
      "lda                                1.0.5      \n",
      "librosa                            0.6.0      \n",
      "lightgbm                           2.2.3      \n",
      "llvmlite                           0.21.0     \n",
      "locket                             0.2.0      \n",
      "lxml                               4.1.1      \n",
      "mahotas                            1.4.5      \n",
      "Markdown                           2.6.11     \n",
      "MarkupSafe                         1.0        \n",
      "matplotlib                         2.1.2      \n",
      "mccabe                             0.6.1      \n",
      "menuinst                           1.4.11     \n",
      "mesh-tensorflow                    0.0.5      \n",
      "missingno                          0.4.1      \n",
      "mistune                            0.8.3      \n",
      "mkl-fft                            1.0.0      \n",
      "mpmath                             1.0.0      \n",
      "msgpack-python                     0.5.1      \n",
      "multipledispatch                   0.4.9      \n",
      "murmurhash                         1.0.2      \n",
      "mysqlclient                        1.4.2.post1\n",
      "navigator-updater                  0.1.0      \n",
      "nbconvert                          5.3.1      \n",
      "nbformat                           4.4.0      \n",
      "networkx                           2.1        \n",
      "nltk                               3.2.5      \n",
      "nose                               1.3.7      \n",
      "notebook                           5.4.0      \n",
      "numba                              0.36.2     \n",
      "numexpr                            2.6.4      \n",
      "numpy                              1.16.4     \n",
      "numpydoc                           0.7.0      \n",
      "oauth2client                       4.1.3      \n",
      "odo                                0.5.1      \n",
      "olefile                            0.45.1     \n",
      "opencv-python                      4.1.0.25   \n",
      "openpyxl                           2.4.10     \n",
      "packaging                          16.8       \n",
      "paddlepaddle                       1.5.0      \n",
      "pandas                             0.22.0     \n",
      "pandas-datareader                  0.7.0      \n",
      "pandas-profiling                   1.4.1      \n",
      "pandocfilters                      1.4.2      \n",
      "parso                              0.1.1      \n",
      "partd                              0.3.8      \n",
      "path.py                            10.5       \n",
      "pathlib2                           2.3.0      \n",
      "pathspec                           0.5.9      \n",
      "patsy                              0.5.0      \n",
      "pbr                                3.1.1      \n",
      "pep8                               1.7.1      \n",
      "pickleshare                        0.7.4      \n",
      "Pillow                             5.0.0      \n",
      "pip                                19.1.1     \n",
      "pipdate                            0.3.1      \n",
      "pivottablejs                       0.9.0      \n",
      "pkginfo                            1.4.1      \n",
      "plac                               0.9.6      \n",
      "pluggy                             0.6.0      \n",
      "ply                                3.10       \n",
      "post                               1.0.2      \n",
      "preshed                            2.0.1      \n",
      "prettytable                        0.7.2      \n",
      "promise                            2.2.1      \n",
      "prompt-toolkit                     1.0.15     \n",
      "protobuf                           3.8.0      \n",
      "psutil                             5.4.3      \n",
      "public                             1.0.3      \n",
      "py                                 1.5.2      \n",
      "py-cpuinfo                         5.0.0      \n",
      "pyasn1                             0.4.5      \n",
      "pyasn1-modules                     0.2.5      \n",
      "PyBrain                            0.3        \n",
      "pycocotools                        2.0        \n",
      "pycodestyle                        2.5.0      \n",
      "pycosat                            0.6.3      \n",
      "pycparser                          2.18       \n",
      "pycrypto                           2.6.1      \n",
      "pycurl                             7.43.0.1   \n",
      "pydot                              1.4.1      \n",
      "pydotplus                          2.0.2      \n",
      "pydub                              0.21.0     \n",
      "pyflakes                           1.6.0      \n",
      "pyglet                             1.3.2      \n",
      "Pygments                           2.2.0      \n",
      "pylint                             1.8.2      \n",
      "pymongo                            3.7.2      \n",
      "PyMySQL                            0.9.3      \n",
      "pyodbc                             4.0.22     \n",
      "pyOpenSSL                          17.5.0     \n",
      "pyparsing                          2.2.0      \n",
      "pypng                              0.0.19     \n",
      "pyproj                             1.9.5.1    \n",
      "pyquery                            1.4.0      \n",
      "pyshp                              1.2.12     \n",
      "PySocks                            1.6.7      \n",
      "pytest                             3.3.2      \n",
      "python-dateutil                    2.6.1      \n",
      "pytz                               2017.3     \n",
      "PyWavelets                         0.5.2      \n",
      "pywin32                            222        \n",
      "pywinpty                           0.5        \n",
      "PyYAML                             3.12       \n",
      "pyzmq                              16.0.3     \n",
      "QtAwesome                          0.4.4      \n",
      "qtconsole                          4.3.1      \n",
      "QtPy                               1.3.1      \n",
      "query-string                       1.0.2      \n",
      "qutip                              4.4.0.dev0 \n",
      "rarfile                            3.0        \n",
      "recordio                           0.1.7      \n",
      "request                            1.0.2      \n",
      "requests                           2.22.0     \n",
      "resampy                            0.2.0      \n",
      "retrying                           1.3.3      \n",
      "rope                               0.10.7     \n",
      "rsa                                4.0        \n",
      "ruamel-yaml                        0.15.35    \n",
      "s3transfer                         0.1.13     \n",
      "scikit-image                       0.15.0     \n",
      "scikit-learn                       0.20.2     \n",
      "scikit-plot                        0.3.7      \n",
      "scipy                              1.0.0      \n",
      "seaborn                            0.9.0      \n",
      "selenium                           3.141.0    \n",
      "Send2Trash                         1.4.2      \n",
      "sequential                         1.0.0      \n",
      "setuptools                         38.4.0     \n",
      "simplegeneric                      0.8.1      \n",
      "singledispatch                     3.4.0.3    \n",
      "six                                1.11.0     \n",
      "smart-open                         1.5.7      \n",
      "snowballstemmer                    1.2.1      \n",
      "sortedcollections                  0.5.3      \n",
      "sortedcontainers                   1.5.9      \n",
      "spacy                              2.1.4      \n",
      "Sphinx                             1.6.6      \n",
      "sphinx-rtd-theme                   0.4.3      \n",
      "sphinxcontrib-websupport           1.0.1      \n",
      "spyder                             3.2.6      \n",
      "SQLAlchemy                         1.2.1      \n",
      "squarify                           0.3.0      \n",
      "srsly                              0.0.5      \n",
      "statsmodels                        0.8.0      \n",
      "structure                          0.1.dev16  \n",
      "sympy                              1.1.1      \n",
      "tables                             3.4.2      \n",
      "tblib                              1.3.2      \n",
      "tensor2tensor                      1.13.4     \n",
      "tensorboard                        1.7.0      \n",
      "tensorflow                         1.7.0      \n",
      "tensorflow-datasets                1.0.2      \n",
      "tensorflow-metadata                0.13.0     \n",
      "tensorflow-probability             0.6.0      \n",
      "termcolor                          1.1.0      \n",
      "terminado                          0.8.1      \n",
      "testpath                           0.3.1      \n",
      "text-unidecode                     1.2        \n",
      "textrank4zh                        0.3        \n",
      "thinc                              7.0.4      \n",
      "tinynetrc                          1.3.0      \n",
      "toml                               0.10.0     \n",
      "toolz                              0.9.0      \n",
      "torch                              0.4.1      \n",
      "torchvision                        0.2.1      \n",
      "tornado                            4.5.3      \n",
      "tqdm                               4.23.0     \n",
      "traitlets                          4.3.2      \n",
      "typing                             3.6.2      \n",
      "unicodecsv                         0.14.1     \n",
      "uritemplate                        3.0.0      \n",
      "urllib3                            1.22       \n",
      "wasabi                             0.2.2      \n",
      "wcwidth                            0.1.7      \n",
      "webencodings                       0.5.1      \n",
      "Werkzeug                           0.14.1     \n",
      "wheel                              0.30.0     \n",
      "widgetsnbextension                 3.1.0      \n",
      "win-inet-pton                      1.0.1      \n",
      "win-unicode-console                0.5        \n",
      "wincertstore                       0.2        \n",
      "wordcloud                          1.5.0      \n",
      "wrapt                              1.10.11    \n",
      "xgboost                            0.7        \n",
      "xlrd                               1.1.0      \n",
      "XlsxWriter                         1.0.2      \n",
      "xlwings                            0.11.5     \n",
      "xlwt                               1.3.0      \n",
      "yapf                               0.26.0     \n",
      "zict                               0.1.3      \n"
     ]
    }
   ],
   "source": [
    "!pip list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "li = [1,2,3,1,1,2,1]\n",
    "c = Counter(li)\n",
    "print(c)\n",
    "s = sorted(c,key = lambda x:x)\n",
    "print(s)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
